A content-addressable memory referred to as a "CAM" below) compares data stored in memory in advance and externally applied search data, determines if there is stored data that matches and extracts the address of the stored data if a match is obtained.
FIG. 6 is a diagram illustrating an example of the structure of a CAM according to the prior art. Here, one bit represents one word, and the CAM is shown in a structure without column.
As shown in FIG. 6, an array of CAM cells A11-Anm are arrayed in the form of a matrix. A selection control line (referred to as a "word line" below) WL1 extending in the row direction of the CAM cells and a match detection signal line (referred to as a "match line" below) ML1, which is for transmitting the result of match operation, extending in the row direction of the CAM cells are commonly connected to all the CAM cells A11-A1m in that row. Word lines WL2-WLn and match lines ML2-MLn are similarly commonly connected to all CAM cells in the corresponding rows. The word lines WL1-WLn are connected to an address decoder 100. The match line ML1 is connected to a match line precharging circuit 111 and to a match detection circuit 103. The other match lines ML2-MLn are similarly connected to match line precharging circuits 112-11n, respectively, and to the match detection circuit 103.
The match detection circuit 103 outputs the address of CAM cells for which a match with search data has been achieved. The match line precharging circuits 111-11n precharge the match lines ML1-MLn connected thereto to a predetermined potential on a per-word-line basis in response to a precharge signal PC from a control circuit 101.
A search data input circuit 120 has a data input line D1 and is controlled by the state of the precharge signal PC from the control circuit 101 to transmit search data to a pair of search data lines CD1, CD1B. Search data input circuits 121-12m are constructed in a manner similar to the search data input circuit 120 and operate in a similar manner.
The pair of search data lines CD1, CD1B are connected to all CAM cells A11-An1 in the corresponding column. Other pairs of search data lines CD2-CDm, CD2B-CDmB are similarly connected to all CAM cells of the corresponding columns.
The address decoder 100, which has input addresses A1-An, is controlled by a signal from the control circuit 101, which has a clock input CLK, and controls the selection of the word lines WL-WLn.
Data is stored in the memory portion of a CAM cell in advance. An example of the stored data is as follows:
WL1 row direction--A11, A12, A13, A1m: 0, 0, 0, 0 PA1 WL2 row direction--A21, A22, A23, A2m: 0, 1, 0, 1 PA1 WLn row direction--An1, An2, An3, Anm: 1, 1, 1, 1 PA1 WL1 row direction--A11, A12, A13, A1m: 0, 0, 0, 0 PA1 WL2 row direction--A21, A22, A23, A2m: 0, 1, 0, 1 PA1 WLn row direction--An1, An2, An3, Anm: 1, 1, 1, 1 then some row-direction CAM cells of the word lines WLn and WL2 will provide a match with search data in case where the search data is 1, 1, 1, 1.
Assume that search data is 1, 1, 1, 1. When all "1"s are applied as the data inputs D1-Dm, the search data is transmitted to all pairs of the search data lines CD1-CDm, CD1B-CDmB, respectively. At such time all bits of the stored data in the row-direction CAM cells An1-Anm of the word line WLn match the search data and a match signal is output on the match line MLn. The address of the row-direction CAM cells An1-Anm of the word line WLn is detected by the match detection circuit 103. When data is read out of another memory device using the detected address, information corresponding to the row-direction CAM data of the word line WLn of the CAM is obtained.
If multiple items of data that have been stored in the memory portions of the CAM cells are identical, e.g.,
If the information that corresponds to the row-direction CAM data of the word line WL2 of the CAM is desired, first the address of the row-direction CAM cells of the word line WLn is detected and information is obtained by reading data out of the other memory device using this address. Next, the address of the row-direction CAM cells of the word line WL2 is detected and data in the other memory device is read out using this address, whereby information corresponding to row-direction CAM data of the word line WL2 of the CAM is obtained. If the data stored in the memory portions of CAM cells provide multiple matches with search data on a per-word line basis, then the number of retrievals will be equivalent to the number of those word lines. The number of retrievals may thus indicate redundancy depending upon the content of the search data.
FIG. 7 is a diagram illustrating the construction of a CAM cell circuit according to the prior art.
As shown in FIG. 7, a CAM cell circuit includes a memory portion (static RAM) 212 and a comparator circuit portion 213 for comparing stored data and search data.
The memory portion 212 and comparator circuit portion 213 include inverters 201, 202 constructing a flip-flop, N-channel MOS transistors (referred to as "NMOS transistors" below) 203, 204, 205, 206, 207, a pair of search data lines CD 208, CD B 209, a word line WL 210 for controlling the writing of data to the memory portion, and a match line ML 211 for outputting whether or not a match is achieved in regard to the stored data and search data on the associated individual word line on the per-word line basis.
FIG. 8 illustrates one word portion of circuitry constituted by the CAM cell circuit shown in FIG. 7.
As shown in FIG. 8, CAM cells 311-31m are identical with the CAM cell shown in FIG. 7 and respective ones of the CAM cells are connected commonly by the pairs of search data lines CD1-CD1B to CDm-CDmB in the column direction.
The search data input circuits 120-12m are provided for respective columns and have data inputs D1-Dm. Further, the search data input circuits 120-12m are controlled by the precharge signal PC and transmit search data on the pairs of search data lines CD1, CD1B and CDm, CDmB. The search data line CDlB transmits data that is the inverse of the data on the search data line CD1.
The match line precharging circuit 111 is composed of a P-channel MOS transistor (referred to as a "PMOS transistor" below). The precharge signal PC enters the gate of this PMOS transistor. One diffusion layer (e.g., the source) is connected to a power supply VDD, and the other diffusion layer (the drain) is connected to match line ML1 of the CAMs in the row direction. The match line precharging circuit is provided for each individual match line in the row direction and precharges the match line in dependence upon the content of the precharge signal PC.
A word structure 321 in the row direction of the CAM cells comprises m-number of CAM cells commonly connected by the word line WL1 and match line ML1 in the row direction. Other word structures 322-32n in the row direction of the CAM cells also are commonly connected by word lines WL2-WLn and match lines ML2-MLn, respectively.
A search and compare operation will now be described with reference to FIG. 7.
In a search and compare operation, the match line ML of the associated word line is charged on the per-word-line basis to the VDD level (power-supply voltage) before search data is transferred on the pair of search data lines CD 208, CDB 209 (where the signal on CDB is the complement of the signal on CD). The search data is transferred to the pair of search data lines CD 208, CDB 209 via the search data input circuit so that a search and compare operation may be performed.
Assume that the search data and the stored data match. If the search data line CD 208 is at the VDD level (the search data line CDB 209, the data of which is the inverse of the data on CD 208, is at the ground GND level) and the stored data at node 214 is at the VDD level (the stored data at node 215 is at the GND level) in FIG. 7, then the NMOS transistor 205 whose gate is provided with the potential at node 214 is rendered conductive (the NMOS transistor 206 is rendered non-conductive) so that the potential on search data line CD 208 is transmitted to the gate of the NMOS transistor 207 via the NMOS transistor 205. Consequently, the gate of the NMOS transistor 207 assumes the high level and the NMOS transistor 207 conducts. The potential on the precharged match line ML 211 is discharged to the ground potential via the NMOS transistor 207.
Assume that the search data and the stored data do not match. If the search data line CD 208 is at the ground level (the search data line CDB 209, the data of which is the inverse of the data on CD 208, is at the VDD level) and the stored data at node 214 is at the VDD level (the stored data at node 215 is at the ground level) in FIG. 7, then the NMOS transistor 205 is rendered conductive (the NMOS transistor 206 is rendered non-conductive) so that the potential of search data line CD 208 is transmitted to the gate of the NMOS transistor 207 via the NMOS transistor 205. The gate of the NMOS transistor 207 reverts to the low level and the NMOS transistor 207 is rendered non-conductive. As a result, the match line ML 211 remains at the precharge potential.
As shown in FIGS. 6 and 8, the CAM cells of each word line are all commonly connected by the match line of that row. Therefore, if the result of a search is a match at any one cell in the row, the match line of the associated word line is discharged to the ground level. If the result of a search is a non-match at all cells, then the match line of the associated word line is held at the precharge potential.
FIG. 9 is a timing chart showing the operation of a CAM circuit according to the prior art. The clock CLK and the precharge signal PC are in synchronization and in phase. When the clock is at the high level (clock 1), this corresponds to the CAM data search interval. When the clock is at the low level (clock 2), this corresponds to the match line precharge interval.
If the VDD level of the precharge signal PC enters the gate of the PMOS transistor in the match line precharging circuit 111, which is constituted by this PMOS transistor, during clock 1 (the CAM data search interval), the PMOS transistor is rendered non-conductive (turned off) and precharging is terminated.
The potential of the precharged match line varies depending upon the result of the data search in the CAM. If the result of the search is a match, the match line goes to ground potential. If the result of the search is a non-match, on the other hand, then the match line is maintained at the precharge potential. Assume that the search data is transmitted to the search data lines at the same time that the clock CLK rises and that the search data does not change in one cycle. When the search data enters from the data input D, the search data is output from the search data input circuit and is transmitted over the pair of search data lines CD, CDB.
If the GND level of the precharge signal PC enters the gate of the PMOS transistor in the match line precharging circuit 111 during clock 2 (the match line precharge interval), the PMOS transistor is rendered conductive (turned on). As a result, the VDD level is transmitted to the match line and the match line of the associated word line is precharged to the VDD level. Further, when the GND level of the precharge signal PC is input to the search data input circuit, the latter transmits the GND potential over the pair of search data lines CD, CDB regardless of the content of the search data. The gate of the NMOS transistor 207, therefore, is turned off and, as a result, the precharge on the match line is not affected.
Cycle A is for a case where the search data and stored data match. Since the result of the search is a match, the match line ML is discharged from the precharge potential to the ground potential in the CAM data search interval of clock 1. When the clock subsequently assumes the low level (clock 2), the match line ML is precharged.
Cycle B is for a case where the search data and stored data do not match. Since the result of the search is a non-match, the match line ML is held at the precharge potential in the CAM data search interval of clock 1. When the clock subsequently assumes the low level (clock 2), a transition is made to the match line precharge interval but the match line remains at the precharge potential.
The determination as to whether the search in the CAM has resulted in a match or non-match is made by detecting the potential level of the match line ML by the match detection circuit 103 of FIG. 6 in the CAM data search interval of clock 1.
A conventional content-addressable memory device disclosed in the specification of Japanese Patent Kokai Publication JP-A-62-293596 (1987) is such that one word is composed of n bits. The device comprises a decoder which performs a word selection for writing in n-bit data, a first content-addressable memory cell array in which one word is composed of m bits, a first sensing amplifier for sensing the result of a comparison performed by the first content-addressable memory cell array, a second content-addressable memory cell array, in which one word is composed of n-m bits, for performing a comparison operation using the output of the first sensing amplifier, and a second sensing amplifier for sensing the results of comparison by the second content-addressable memory cell array in dependence upon the output of the first sensing amplifier, whereby it is intended that less power is consumed at the time of the comparison operation.